//////////////////////////////////////////////////////////////////////////////////
//                                                                              //
//  This file is part of the buola project (https://code.google.com/p/buola/).  //
//                                                                              //
//  Copyright(c) 2007-2011 Xavi Gratal                                          //
//  gratal AT gmail DOT com                                                     //
//                                                                              //
//  Buola is free software: you can redistribute it and/or modify               //
//  it under the terms of the GNU General Public License as published by        //
//  the Free Software Foundation, either version 3 of the License, or           //
//  (at your option) any later version.                                         //
//                                                                              //
//  Buola is distributed in the hope that it will be useful,                    //
//  but WITHOUT ANY WARRANTY; without even the implied warranty of              //
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               //
//  GNU General Public License for more details.                                //
//                                                                              //
//  You should have received a copy of the GNU General Public License           //
//  along with buola.  If not, see <http://www.gnu.org/licenses/>.              //
//                                                                              //
//////////////////////////////////////////////////////////////////////////////////

#ifndef _BUOLA_ALGORITHM_HASH_H_
#define _BUOLA_ALGORITHM_HASH_H_

#include <buola/buola.h>
#include <unordered_set>

namespace buola {

///\addtogroup algorithm
///@{

///\name Hashing
//@{

///combines a new hash value with an existing one

///The implementation is copied from the one in the boost library.
///
///It computes the hash of \p pValue, and combines this hash with the one already present in \p pSeed.
///The result is stored in \p pSeed.
///
///An example usage can be seen in \ref APairHash
template<typename tType,typename tHash=std::hash<tType>>
inline void hash_combine(std::size_t &pSeed,const tType &pValue)
{
    tHash lHasher;
    pSeed^=lHasher(pValue)+0x9e3779b9+(pSeed<<6)+(pSeed>>2);
}

/////////////////////////////////////////////////////////////////////////////////////////////////

/// function class to compute the hash for a \c std::pair

/// Combines the hash of both members of the pair into a single hash value
///
/// The C++ standard requires specializations of \c std::hash to expose the type of its arguments
/// as \c std::unary_function does, but it doesn't impose this requirement to the classes that 
/// are passed as template parameters to, e.g. \c std::unordered_set. This requirement would make
/// it impossible to use a templatized \c operator() but it seems valid to do it here.
///
/////////////////////////////////////////////////////////////////////////////////////////////////

struct APairHash
{
    ///uses \ref hash_combine to combine the hash values of the two members of the pair
    
    ///The hash of each member is computed using \c std::hash
    template<typename tA,typename tB>
    std::size_t operator()(const std::pair<tA,tB> &pPair) const
    {
        std::hash<tA> lAHasher;
        std::size_t lHash=lAHasher(pPair.first);
        hash_combine(lHash,pPair.second);
        return lHash;
    }
};

//@}

///@}

/*namespace buola*/ }

#endif
